Khởi công xây dựng ngày 3 tháng 2 năm 2005, dự kiến khánh thành tháng 5 năm 2007. Nhưng do khó khăn về công tác giải phóng mặt bằng nên tiến độ khánh thành cầu đã bị chậm lại, sau đó có thông báo dự kiến hợp long cầu vào dịp tết âm lịch 2008. Tuy nhiên đến tháng 1/2008 ban quản lý lại tiếp tục thông báo đẩy lùi tiến độ do một số nguyên nhân và không thông báo ngày hoàn thành.
Ngày 25 tháng 9 năm 2009, thủ tướng Nguyễn Tấn Dũng đã chính thức cắt băng khánh thành thông xe cây cầu rộng nhất Việt Nam này (giữ kỷ lục này đến khi Cầu Đông Trù được khánh thành vào 09/10/2014).[1]
Ngày 26 tháng 9 năm 2010, cầu Vĩnh Tuy chính thức được khánh thành giai đoạn 1.[2]
Ngày 9 tháng 1 năm 2021, cầu Vĩnh Tuy giai đoạn 2 được khởi công xây dựng và dự kiến hoàn thành một năm sau đó (2022).
